#include <stdio.h>
#include <stdlib.h>
#include "DynamicArray.h"

#define true 1
#define false 0
int Initialize(struct DynamicArray *array)
{
    array->dp = (ElementType *)malloc(sizeof(ElementType) * array->size);
    if(array->dp == NULL)
    {
        printf("malloc error!\n");
        return false;
    }
    return true;
}

void FreeArray(struct DynamicArray *array)
{
    if(array->dp != NULL)
    {
        free(array->dp);
        array->dp = NULL;
        array->len = 0;
    }
}

int ReallocArray(struct DynamicArray *array)
{
    ElementType *temp = array->dp;
    array->size = array->size * 2;
    array->dp = (ElementType *)malloc(sizeof(ElementType) * array->size);
    if(array->dp == NULL)
    {
        printf("ReallocArray error!\n");
        array->dp = temp;
        array->size = array->size / 2;
        return false;
    }

    for(int i = 0; i < array->len; i++)
    {
        array->dp[i] = temp[i];
    }

    Free(temp);
    return true;

}


int InsertArray(struct DynamicArray *array,ElementType element)
{
    if(array->len == array->size)
    {
        if(ReallocArray(array) == false)
        {
            printf("can not  contain more elements!\n");
            return false;
        }
    }
    array->dp[array->len] = element;
    array->len++;
    return true;
}

void Travel(ElementType *a,int len)
{
    for(int i=0;i<len;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");

}

void ReTravel(ElementType *a,int len)
{
    for(int i=len-1;i>=0;i--)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
}

void InsertTail(struct DynamicArray *array,ElementType element)
{
    if(array->len>=array->size)
    {
        if(ReallocArray(array) == false)
        {
            printf("can not  contain more elements!\n");
            return;
        }
    }
    array->dp[array->len]=element;
    array->len++;
}

void InsertHead(struct DynamicArray *array,ElementType element)
{
    if(array->len>=array->size)
    {
        if(ReallocArray(array) == false)
        {
            printf("can not  contain more elements!\n");
            return;
        }
    }   
    
    for(int i=array->len;i>0;i--)
    {
        array->dp[i]=array->dp[i-1];
    }
    array->dp[0]=element;
    array->len++;
}

void InsertIndex(struct DynamicArray *array,ElementType element,int index)
{
    if(array->len>=array->size)
    {
        if(ReallocArray(array) == false)
        {
            printf("can not  contain more elements!\n");
            return;
        }
    }   

    if(index<0 || index>array->len)
    {
        printf("invalid place!\n");
        return;      
    }

    for(int i=array->len;i>index;i--)
    {
        array->dp[i]=array->dp[i-1];
    }

    array->dp[index]=element;
    array->len++;
}

void RemoveIndex(struct DynamicArray *array,int index)
{
    if(index<0 || index>=array->len)
    {
        printf("invalid place!\n");
        return;      
    }

    for(int i=index+1;i<array->len;i++)
    {
        array->dp[i-1]=array->dp[i];
    }
    array->len--;
}

void RemoveElement(struct DynamicArray *array,ElementType element)
{
    for(int i=0;i<array->len;i++)
    {
        if(array->dp[i]==element)
        {
            RemoveIndex(array,i);
        }
    }
}

ElementType FindByIndex(struct DynamicArray *array,int index)
{
    if(index<0 || index>=array->len)
    {
        printf("invalid place!\n");
        return 0;      
    }    

    return array->dp[index];
}

int* FindByElement(struct DynamicArray*array,ElementType element)
{
    int* findVector=(int *)malloc((array->len+1)*sizeof(ElementType));
    int count=0;
    for(int i=0;i<array->len;i++)
    {
        if(array->dp[i]==element)
        {
            count++;
            findVector[count]=i;
        }
    }
    findVector[0]=count;
    return findVector;
}

int* FindByElement2(struct DynamicArray*array,ElementType element)
{
    int* findVector=(int *)malloc((array->len+1)*sizeof(ElementType));
    int count=0;
    for(int i=0;i<array->len;i++)
    {
        if(array->dp[i]==element)
        {
            findVector[count]=i;
            count++;
        }
    }
    findVector[count]=-1;
    return findVector;
}

void SetValueByIndex(struct DynamicArray *array,int index,ElementType element)
{
    if(index<0 || index>=array->len)
    {
        printf("invalid place!\n");
        return;      
    }   
    array->dp[index]=element;
}

void SetValueByElement(struct DynamicArray *array,ElementType old_value,ElementType new_value)
{
    for(int i=0;i<array->len;i++)
    {
        if(array->dp[i]==old_value)
        {
            array->dp[i]=new_value;
        }
    }
}

struct DynamicArray* FindIntersection(struct DynamicArray *array1,struct DynamicArray *array2)
{
    struct DynamicArray *intersection=(struct DynamicArray *)malloc(sizeof(struct DynamicArray));
    if(intersection==NULL)
        return NULL;
    for(int i=0;i<array1->len;i++)
    {
        for(int j=0;j<array2->len;j++)
        {
            if(array1->dp[i]==array2->dp[j])
            {
                int flag=0;
                for(int k=0;k<intersection->len;k++)
                {
                    if(intersection->dp[k]==array1->dp[i])
                    {
                        flag=1;
                    }
                }
                if(flag==0)
                {
                    InsertTail(intersection,array1->dp[i]);
                }

            }
        }

    }
    return intersection;
}

void Deduplication(struct DynamicArray *array)
{
    fastSort(array->dp,0,array->len-1);
    for(int i=0;i<array->len-1;i++)
    {
        if(array->dp[i+1]==array->dp[i])
        {
            RemoveIndex(array,i+1);
            i--;
        }
    }
}

struct DynamicArray* FindUnionSet(struct DynamicArray *array1,struct DynamicArray *array2)
{
    struct DynamicArray *unionset=(struct DynamicArray *)malloc(sizeof(struct DynamicArray));
    if(unionset==NULL)
        return NULL;
    for(int i=0;i<array1->len;i++)
    {
        InsertTail(unionset,array1->dp[i]);
    }
    for(int i=0;i<array2->len;i++)
    {
        InsertTail(unionset,array2->dp[i]);
    }
    Deduplication(unionset);
    return unionset;
}

struct DynamicArray* MergeArray(struct DynamicArray *array1,struct DynamicArray *array2)
{
    fastSort(array1->dp,0,array1->len-1);
    fastSort(array2->dp,0,array2->len-1);
    struct DynamicArray *Merge=(struct DynamicArray *)malloc(sizeof(struct DynamicArray));
    Merge->len=0;
    if(Merge==NULL)
        return NULL;   
    int i=0,j=0;
    while(i<array1->len && j<array2->len)
    {
        if(array1->dp[i]<=array2->dp[j])
        {
            InsertTail(Merge,array1->dp[i]);
            i++;
        }
        else
        {
            InsertTail(Merge,array2->dp[j]);
            j++;
        }
    }
    while(i<array1->len)
    {
        InsertTail(Merge,array1->dp[i]);
        i++;
    }
    while(j<array2->len)
    {
        InsertTail(Merge,array2->dp[j]);
        j++;
    }
    return Merge;
}

int IsBigger(int a,int b)
{
    if(a>b)
        return 1;
    else 
        return 0;
}

//54321
int IsSmaller(int a,int b)
{
    if(a<b)
        return 1;
    else 
        return 0;
}

void Swap(int *a,int *b)
{
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}

// 1.
void BubbleSort(int *a,int len,int (*Rule)(int,int))
{
    for(int i=0;i<len-1;i++)
    {
        int flag=0;
        for(int j=0;j<len-i-1;j++)
        {
            if(Rule(a[j],a[j+1]))
            {
                int temp;
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
                flag=1;
            }
        }
        if(flag==0)
        {
            break;
        }
    }
}

// 2.
void InsertSort(int *a,int len)
{
    for(int i=0;i<len;i++)
    {
        int temp=a[i];
        int j=i;
        for(;j>0;j--)
        {
            if(a[j-1]>temp)
            {
                a[j]=a[j-1];
            }
            else
                break;
        }
        a[j]=temp;
    }
}

// 3.
void ChooseSort(int *a,int len)
{
    int left=0;
    int right=len-1;
    while(left<right)
    {
        int min=left;
        int max=right;
        for(int i=left;i<=right;i++)
        {
            if(a[i]<a[min])
                min=i;
            if(a[i]>a[max])
                max=i;
        }
        Swap(&a[left],&a[min]);
        if(max==left)
        {
            max=min;
        }
        Swap(&a[right],&a[max]);

        left++;
        right--;
    }
}

// 4.
// fastSort(a,0,ArrayLen(a)-1);
void fastSort(int *a,int start,int end)
{
    int left=start;
    int right=end;
    int temp=a[start];
    while(left<right)
    {
        while(left<right && a[right]>temp)
        {
            right--;
        }

        if(left<right)
        {
            a[left]=a[right];
            left++;
        }

        while(left<right && a[left]<temp)
        {
            left++;
        }

        if(left<right)
        {
            a[right]=a[left];
            right--;
        }

        a[left]=temp;
        fastSort(a,start,left-1);
        fastSort(a,right+1,end);
    }   
}